#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>


struct ListNode
{
    int       val;
    ListNode *next;
    ListNode(int value) : val(value), next(nullptr) {};
};


ListNode* bulidRandomList()
{
    ListNode dumy(-1), *cur = &dumy;
    srand(time(0));
    for(int i = 0; i < 3; i ++)
    {
        cur->next = new ListNode(rand() % 100); 
        cur = cur->next;  
    }

    return dumy.next;

}

void destoryList(ListNode *head)
{
    ListNode *next = nullptr;
    while(head)
    {
        next = head->next;
        delete head;
        head = next;
    }
}

void printList(ListNode* head)
{
    ListNode *cur = head;
    while(cur)
    {
        std::cout<< cur->val <<"->";
        cur = cur->next;
    }
    std::cout<< "nullptr"<<std::endl;
}


ListNode* divideList(ListNode* head)
{
    if(head == nullptr || head->next == nullptr)
        return head;
    ListNode *slow = head, *fast = head;

    while(fast->next && fast->next->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    } 
    ListNode *newList = slow->next;
    slow->next = nullptr;
    return newList;
}
ListNode *reverseList(ListNode *head)
{
    if(head == nullptr || head->next == nullptr)
        return head;
    ListNode *prev = nullptr;
    ListNode *cur = head;

    while(cur)
    {
        ListNode *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}



void reorderList(ListNode *head)
{
    if(head == nullptr || head->next == nullptr)
        return;
    ListNode *rList = divideList(head);
    rList = reverseList(rList);

    
    //merge list
    while(head)
    {
        ListNode *rNext = nullptr, *lNext = nullptr; 
        lNext = head->next;
        if (rList) 
            rNext = rList->next;
        else
            break;

        head->next = rList;
        rList->next = lNext;
        rList = rNext;
        head = lNext;
    }
}
ListNode* partition(ListNode* head, int x) {
    ListNode lessList(-1), greaterList(-1), eqList(-1);
    ListNode *l = &lessList, *g = &greaterList;
    ListNode *cur = head, *px = &eqList;
    while(cur)
    {
        if(cur->val < x)
        {
            l->next = cur;
            l = l->next;
        }
        else if(cur->val == x)
        {
            px->next = cur;
            px = px->next;
        }
        else
        {
            g->next = cur;
            g = g->next;
        }
        cur = cur->next;
    }
    //link all list
    l->next = eqList.next ? eqList.next : greaterList.next;
    px->next = greaterList.next;
    return lessList.next;
}
